package com.example.leetcode.trainingcamp.week7.Thursday;

/**
 * 返回与给定的前序和后序遍历匹配的任何二叉树。
 *
 * <p>pre 和 post 遍历中的值是不同的正整数。
 */
public class Test889 {

    // pre= [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return myTreeBuild(preorder,0,preorder.length-1,postorder,0,postorder.length-1);
    }


    public TreeNode myTreeBuild(int[] preorder,int i,int j ,int[] postorder,int k,int l){
        if (i > j) return null;
        TreeNode root = new TreeNode(preorder[i]);
        if (i == j) return root;
        int s = k;
        while (s <= l &&  preorder[i+1] != postorder[s]){
            s++;
        }
        int size = s - k;
        TreeNode left = myTreeBuild(preorder,i+1,i+size+1,postorder,k,k+size);
        TreeNode right  = myTreeBuild(preorder,i+size+2,j,postorder,k+size+1,l-1);
        root.left = left;
        root.right = right;
        return root;
    }
}
